package linkedList;

/**
 * 合并 K 个升序链表 -23
 *
 * @author yyz
 * @create 2023-11-22 16:03
 */
public class 合并K个升序链表 {
    public static void main(String[] args) {
        ListNode[] lists = {
                ListNode.of(1, 2),
                ListNode.of(3, 3, 4),
                ListNode.of(1, 2)
        };
        System.out.println(new 合并K个升序链表().mergeKLists2(lists));
    }

    /**
     * 小顶堆 父节点比子节点<b>小</b>
     */
    static class minHeap {
        ListNode[] array;
        int size = 0;

        public minHeap(int capacity) {
            array = new ListNode[capacity];
        }

        public boolean offer(ListNode value) {
            if (isFull()) {
                return false;
            }
            int chalid = size++;
            int parent = (chalid - 1) / 2;
            while (chalid > 0 && value.val < array[parent].val) {
                array[chalid] = array[parent];
                chalid = parent;
                parent = (chalid - 1) / 2;
            }
            array[chalid] = value;
            return true;
        }

        public ListNode poll() {
            if (isEmpty()) {
                return null;
            }
            ListNode val = array[0];
            // 交换0索引和size-1索引值
            swap(0, size - 1);
            array[--size] = null;

            // 下潜
            down(0);
            return val;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return size == array.length;
        }

        private void swap(int i, int j) {
            ListNode t = array[i];
            array[i] = array[j];
            array[j] = t;
        }

        private void down(int index) {
            int left = 2 * index + 1;
            int right = left + 1;
            int max = index;
            if (left < size && array[max].val > array[left].val) {
                max = left;
            }
            if (right < size && array[max].val > array[right].val) {
                max = right;
            }
            if (max != index) {
                swap(index, max);
                down(max);
            }
        }
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        minHeap m = new minHeap(lists.length);
        for (ListNode list : lists) {
            if (list != null) {
                m.offer(list);
            }
        }

        ListNode s = new ListNode(-1, null);
        ListNode t = s;
        while (!m.isEmpty()) {
            ListNode poll = m.poll();
            t.next = poll;
            t = t.next;
            if (poll.next != null) {
                m.offer(poll.next);
            }
            t.next = null;
        }
        return s.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        // 如果数组为空，返回null
        if (lists.length == 0) {
            return null;
        }
        // 调用split方法，将链表数组分为两个部分，再调用mergeTwoLists方法进行合并
        return split(lists, 0, lists.length - 1);
    }

    private ListNode split(ListNode[] lists, int i, int j) {
        // 如果只有一个链表，直接返回该链表
        if (i == j) {
            return lists[i];
        }

        // 将链表数组分为两半
        int m = (i + j) >>> 1;
        // 分别对左右两半调用split方法，得到合并后的两个链表
        ListNode left = split(lists, i, m);
        ListNode right = split(lists, m + 1, j);

        // 调用mergeTwoLists方法将左右两个链表合并
        return mergeTwoLists(left, right);
    }


    //合并两个有序链表
    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode s = new ListNode(-1);
        ListNode p = s;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                s.next = list1;
                list1 = list1.next;
            } else {
                s.next = list2;
                list2 = list2.next;
            }
            s = s.next;
        }
        s.next = (list1 != null ? list1 : list2);

        return p.next;
    }
}
